package datastructure.book.dp._1_pathway.exercise.second;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _9_Solution {
    /**
     * 给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。
     * 你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。
     * 在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。
     * 一条路径的 「得分」 定义为：路径上所有数字的和。
     * 请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，
     * 请把结果对 10^9 + 7 取余。
     * 如果没有任何路径可以到达终点，请返回 [0, 0] 。
     * 2 <= board.length == board[i].length <= 100
     * 例：
     * E51
     * 12X
     * 3XS
     * 得分最大路径  S->2->5->E  结果为[7,1]
     * E12
     * 121
     * 21S
     * 结果为[4,6]
     */
    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        char[][] chars = new char[n][n];
        for (int i = 0; i < board.size(); i++) {
            chars[i] = board.get(i).toCharArray();
        }
        int[][] dpScore = new int[2][n];
        int[][] dpCnt = new int[2][n];
        int pre = 0;int cur = 1;
        dpCnt[0][n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            char curChar = chars[n - 1][i];
            if (curChar == 'X') {
                break;
            }
            dpCnt[0][i] = 1;
            dpScore[0][i] = dpScore[0][i+1]+(curChar-'0');
        }
        for (int i = n-2; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                char curChar = chars[i][j];
                if (curChar == 'X') {
                    dpCnt[cur][j] = 0;
                    continue;
                }
                int rightScore = getScore(i,j+1,n,dpCnt[cur],dpScore[cur]);
                int downScore = getScore(i+1,j,n,dpCnt[pre],dpScore[pre]);
                int rightDownScore = getScore(i+1,j+1,n,dpCnt[pre],dpScore[pre]);
                int maxScore = this.max(rightScore,downScore,rightDownScore);
                if (maxScore == -1) {
                    dpCnt[cur][j] = 0;
                    continue;
                }
                dpScore[cur][j] = maxScore + (curChar-'0');
                int cnt = 0;
                if (rightScore == maxScore) {
                    cnt+=dpCnt[cur][j+1];
                    cnt%=1000000007;
                }
                if (downScore == maxScore) {
                    cnt+=dpCnt[pre][j];
                    cnt%=1000000007;
                }
                if (rightDownScore == maxScore) {
                    cnt+=dpCnt[pre][j+1];
                    cnt%=1000000007;
                }
                dpCnt[cur][j] = cnt;
            }
            int temp = pre;
            pre = cur;
            cur = temp;
        }
        if (dpCnt[pre][0] == 0) {
            return new int[]{0, 0};
        } else {
            return new int[]{dpScore[pre][0]-'E'+'0', dpCnt[pre][0]};
        }
    }

    private int max(int a, int b, int c) {
        return Math.max(Math.max(a,b),c);
    }

    private int getScore(int i, int j, int n, int[] dpCnt, int[] dpScore) {
        if (i < n && j < n && dpCnt[j] > 0) {
            return dpScore[j];
        }
        return -1;
    }

    @Test
    public void test(){
        List<String> board = new ArrayList<>();
        board.add("E11");
        board.add("XXX");
        board.add("21S");
        System.out.println(Arrays.toString(pathsWithMaxScore(board)));
        board = new ArrayList<>();
        board.add("E1222X");
        board.add("XXXXX5");
        board.add("211674");
        board.add("312671");
        board.add("312671");
        board.add("31267S");
        System.out.println(Arrays.toString(pathsWithMaxScore(board)));
    }
}
